/**
 * 
 */
package array;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author xyyi
 * 
 */
/*
 * A long array A[] is given to you. There is a sliding window of size w which
 * is moving from the very left of the array to the very right. You can only see
 * the w numbers in the window. Each time the sliding window moves rightwards by
 * one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and
 * w is 3.
 * 
 * Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5
 * 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3
 * -1 -3 5 [3 6 7] 7 Input: A long array A[], and a window width w Output: An
 * array B[], B[i] is the maximum value of from A[i] to A[i+w-1] Requirement:
 * Find a good optimal way to get B[i]
 * 
 * http://leetcode.com/2011/01/sliding-window-maximum.html
 */
public class SlidingWindowsMax {

	public int[] maxSlidingWindow(int[] arr, int wSize) {
		// TODO
		return maxSlidingWindowDueue(arr, wSize);
	}

	// time O(nlogn), n: size for arr, w: window size
	public int[] maxSlidingWindowHeap(int[] arr, int wSize) {
		if (arr == null || arr.length < wSize) {
			return null;
		}

		PriorityQueue<int[]> heap = new PriorityQueue<int[]>();
		for (int i = 0; i < wSize; i++) {
			int[] pair = new int[2];
		}

		return null;
		// TODO
	}

	// time O(n), n: size for arr, w: window size
	public int[] maxSlidingWindowDueue(int[] arr, int wSize) {
		if (arr == null || arr.length < wSize) {
			return null;
		}

		int[] result = new int[arr.length - wSize + 1];
		Queue<Integer> deque = new LinkedList<Integer>();
		for (int i = 0; i < wSize - 1; i++) {
			while (!deque.isEmpty() && arr[deque.peek()] <= arr[i]) {
				deque.poll();
			}
			deque.add(i);
		}

		for (int i = wSize - 1; i < arr.length; i++) {
			while (!deque.isEmpty() && arr[deque.peek()] <= arr[i]) {
				deque.poll();
			}
			deque.add(i);
			while (!deque.isEmpty() && arr[deque.peek()] < i - wSize + 1) {
				deque.poll();
			}
			result[i - wSize + 1] = arr[deque.peek()];
		}

		return result;
	}

	// time O(nw), n: size for arr, w: window size
	public int[] maxSlidingWindowBF(int[] arr, int wSize) {
		if (arr == null || arr.length < wSize) {
			return null;
		}

		int[] result = new int[arr.length - wSize + 1];
		for (int i = 0, size = arr.length - wSize; i <= size; i++) {
			result[i] = max(arr, i, i + wSize - 1);
		}

		return result;
	}

	private int max(int[] arr, int from, int to) {
		assert (arr != null && from >= 0 && from < to && to < arr.length);

		int currentMax = arr[0];
		for (int i = from; i <= to; i++) {
			currentMax = arr[i] > currentMax ? arr[i] : currentMax;
		}

		return currentMax;
	}

	/**
	 * 
	 */
	public SlidingWindowsMax() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = { 1, 3, -1, -3, 5, 3, 6, 7 };
		int windowSize = 3;
		int[] answer = { 3, 3, 5, 5, 6, 7 };

		SlidingWindowsMax swm = new SlidingWindowsMax();
		int[] result = swm.maxSlidingWindowDueue(arr, windowSize);
		for (int i : result) {
			System.out.printf("%d,", i);
		}
		System.out.println("the result is " + Arrays.equals(result, answer));

	}
}
